

//三步问题
#define NUM 1000000007
class Solution {
public:
    void InitDpList(vector<size_t>& dp, int n) {
        dp[0] = 0;
        dp[1] = 1;
        if (n >= 2)
            dp[2] = 2;
        if (n >= 3)
            dp[3] = 4;
    }
    int waysToStep(int n) {
        vector<size_t> dp(n + 1);
        InitDpList(dp, n);
        for (size_t i = 4; i <= n; ++i) {
            
            dp[i] = ((dp[i - 3])%NUM + (dp[i - 2])%NUM + (dp[i - 1])%NUM)%NUM;
            dp[i]%=NUM;
        }
        // dp表达式：dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
        return dp[n];
    }
};
//最小花费爬楼梯
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<size_t> dp(cost.size(),0);
        if(cost.size() < 3)
            return min(dp[0]+cost[0],dp[1]+cost[1]);
        for(size_t i = 2 ; i < dp.size() ; ++i)
        {
            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }

        size_t end = dp.size()-1;
        return min(dp[end]+cost[end],dp[end-1]+cost[end-1]);
    }
};
//解码方法
class Solution {
public:
    int numDecodings(string s) {
        vector<size_t> dp(s.size());
        // 状态表示：以i位置为结尾，解码方法的总数
        // 状态转移方程：dp[i] = dp[i-1] + dp[i-2](必须解码成功，否则0)
        auto NumLegal = [](int num) {
            if (num >= '1' && num <= '9')
                return true;
            return false;
        };
        auto CodeLegal = [](int num) {
            if (num >= 10 && num <= 26)
                return true;
            return false;
        };
        // 1、初始化
        if (NumLegal(s[0])) {
            dp[0] = 1;
            if (s.size() > 1) {
                if (NumLegal(s[1]))
                    dp[1] = 1;
                int temp = (s[0] - '0') * 10 + (s[1] - '0');
                if (CodeLegal(temp))
                    dp[1]++;
            }
        } else {
            return 0;
        }
        // 填表
        for (size_t i = 2; i < s.size(); ++i) {
            if (NumLegal(s[i]))
                dp[i] += dp[i - 1];
            int temp = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if (CodeLegal(temp))
                dp[i] += dp[i - 2];
        }
        return dp[dp.size() - 1];
    }
};